// https://leetcode-cn.com/problems/implement-trie-prefix-tree/
// 208. Implement Trie (Prefix Tree)
// A trie or prefix tree is a tree data structures used to
// efficiently store and retrieve keys in a dataset of strings.
// Implement the Trie class:
// - Trie() Initializes the trie object.
// - void insert(String word) inserts the string word into the trie
// - boolean search(String word), Returns true if the string word is in the trie
// - boolean startsWith(String prefix) Returns true if there is a previously inserted
// string word that has the prefix.

class Trie {
    children: Record<string, any>;
    constructor() {
        this.children = {};
    }

    insert(word: string): void {
        let node = this.children;
        for (let c of word) {
            if (node[c] === undefined) {
                node[c] = {};
            }
            node = node[c];
        }
        node.isEnd = true;
    }

    searchPrefix(prefix: string): any {
        let node = this.children;
        for (let c of prefix) {
            if (node[c] === undefined) return false;
            node = node[c];
        }
        return node;
    }

    search(word: string): boolean {
        const node = this.searchPrefix(word);
        return node !== undefined && node.isEnd === true;
    }

    startsWith(prefix: string): boolean {
        return !!this.searchPrefix(prefix);
    }
}
